#include <bits/stdc++.h>
#pragma	GCC	optimize(3)

using namespace std;

struct node
{
	int	val,size,key,cnt; node	*l,*r; node() {}
	node(const int x) { val=x,size=1,key=rand(),cnt=1;l=r=0; }
} U[310000],*Trash[310000];
int top,ALL;

node*	ALLOC() { return top?Trash[top--]:U+(++ALL); }
void	RECYCLE(node * t) { Trash[++top]=t; return ; }

int	a[21000],n,m;

struct Treap
{
	node * root;

	Treap() { root=0; }

	void	update(node * t)
	{
		t->size=(t->l?t->l->size:0)+
			(t->r?t->r->size:0)+t->cnt;
	}

	void	lturn(node *& t)
	{ node * temp=t; t=t->r; temp->r=t->l;
		t->l=temp; update(t->l); update(t); }
	void	rturn(node *& t)
	{ node * temp=t; t=t->l; temp->l=t->r;
		t->r=temp; update(t->r); update(t); }

	void	insert(node *& t,const int d)
	{
		if(!t)return t=ALLOC(),*t=node(d),(void)0;
		if(t->val==d)return t->cnt++,t->size++,(void)0;
		t->size++;
		if(t->val>d) { insert(t->l,d); if(t->l->key>t->key)rturn(t); }
		else  { insert(t->r,d); if(t->r->key>t->key)lturn(t); } return ;
	}

	void	erase(node *& t,const int d)
	{
		if(!t)return ;
		if(t->val==d)
		{
			if(t->cnt>1)return t->cnt--,t->size--,(void)0;
			if(!t->l || !t->r)
			{
				node *temp=t;
				t=(t->l?t->l:(t->r?t->r:0));
				RECYCLE(temp);
			}
			else if(t->l->key<t->r->key)rturn(t),erase(t,d);
			else	lturn(t),erase(t,d);
		}
		else if(d>t->val)t->size--,erase(t->r,d);
		else	t->size--,erase(t->l,d); return ;
	}

	int	get_rank(node * t,const int pos,const int step)
	{
		if(!t)return step;
		if(pos==t->val)return step+(t->l?t->l->size:0);
		else if(pos<t->val)return get_rank(t->l,pos,step);
		return get_rank(t->r,pos,step+(t->l?t->l->size:0)+t->cnt);
	}

	int	get_r_rank(node * t,const int pos,const int step)
	{
		if(!t)return step;
		if(pos==t->val)return step+(t->r?t->r->size:0);
		else if(pos>t->val)return get_r_rank(t->r,pos,step);
		return get_r_rank(t->l,pos,step+(t->r?t->r->size:0)+t->cnt);
	}

	void	insert(const int x) { insert(root,x); return; }
	void	erase(const int x) { erase(root,x); return ; }
	int	get_rank(const int x) { return get_rank(root,x,0); }
	int	get_r_rank(const int x) { return get_r_rank(root,x,0); }
} S[71000];

int	Query_less(const int l,const int r,const int num,const int s,const int t,const int d)
{
	if(s>t)return 0; if(s<=l && r<=t) { return S[num].get_rank(d); }
	int	mid=l+((r-l)>>1);
	if(t<=mid)return Query_less(l,mid,num<<1,s,t,d);
	if(s>mid) return Query_less(mid+1,r,num<<1|1,s,t,d);
	return Query_less(l,mid,num<<1,s,t,d)+Query_less(mid+1,r,num<<1|1,s,t,d);
}

int	Query_greater(const int l,const int r,const int num,const int s,const int t,const int d)
{
	if(s>t)return 0; if(s<=l && r<=t) { return S[num].get_r_rank(d); }
	int	mid=l+((r-l)>>1);
	if(t<=mid)return Query_greater(l,mid,num<<1,s,t,d);
	if(s>mid) return Query_greater(mid+1,r,num<<1|1,s,t,d);
	return Query_greater(l,mid,num<<1,s,t,d)+Query_greater(mid+1,r,num<<1|1,s,t,d);
}

void	Change(const int l,const int r,const int num,const int s,const int d,const int dd)
{
	if(l==r) { S[num].erase(d); S[num].insert(dd); return ; }
	int	mid=l+((r-l)>>1);
	if(s<=mid)Change(l,mid,num<<1,s,d,dd);
	else	Change(mid+1,r,num<<1|1,s,d,dd);
	S[num].erase(d),S[num].insert(dd);
	return ;
}

void	Build(const int l,const int r,const int num)
{
	if(l==r)return S[num].insert(a[l]),(void)0;
	int	mid=l+((r-l)>>1);
	Build(l,mid,num<<1); Build(mid+1,r,num<<1|1);
	for(int i=l; i<=r; ++i)S[num].insert(a[i]); return ;
}
void	Init_Ans(int &	Ans)
{
	Ans=0;
	for(int i=2; i<=n; ++i)
		Ans+=Query_greater(1,n,1,1,i,a[i]);
	return ;
}

int	getint()
{
	int	data=0;char ch=getchar(); while(ch>'9' || ch<'0')ch=getchar_unlocked();
	while(ch>='0' && ch<='9')data=data*10+ch-48,ch=getchar_unlocked(); return data;
}

int main()
{
	int	i,Ans,x,y;

	n=getint();
	for(i=1; i<=n; ++i)a[i]=getint();
	Build(1,n,1); Init_Ans(Ans);
	m=getint(); printf("%d\n",Ans);
	while(m--)
	{
		x=getint(),y=getint();
		if(x>y)swap(x,y);
		Ans-=Query_less(1,n,1,x+1,y-1,a[x])+Query_greater(1,n,1,x+1,y-1,a[y]);
		Ans+=Query_less(1,n,1,x+1,y-1,a[y])+Query_greater(1,n,1,x+1,y-1,a[x]);
		Ans-=a[x]>a[y]; Ans+=a[x]<a[y];
		Change(1,n,1,x,a[x],a[y]); Change(1,n,1,y,a[y],a[x]);
		swap(a[x],a[y]); printf("%d\n",Ans);
	}
	return 0;
}
